package org.lql.algo.codecrush.week005;

/**
 * @author: liangqinglong
 * @date: 2025-08-05 17:56
 * @description: 面试题 08.05. 递归乘法 <a href="https://leetcode.cn/problems/recursive-mulitply-lcci/description/">...</a>
 **/
public class Multiply {


	/**
	 * 递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：A = 1, B = 10
	 * 输出：10
	 * 示例 2：
	 * <p>
	 * 输入：A = 3, B = 4
	 * 输出：12
	 * 提示：
	 * <p>
	 * 保证乘法范围不会溢出
	 */
	public int multiply(int A, int B) {
		if (B == 0) {
			return 0;
		}
		if (B > 0) {
			return A + multiply(A, B - 1);
		}
		return -multiply(A, -B);
	}

	public static void main(String[] args) {
		Multiply multiply = new Multiply();
		System.out.println(multiply.multiply(3, 4));
	}
}
